package 单周赛.september;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @
 * @date 2024/09/22
 */
public class 第416场力扣周赛 {

    public static void main(String[] args) {
        Set<String> bSet = new HashSet<>();
        bSet.add("hello");
        System.out.println(bSet.contains("hello"));

        System.out.println(reportSpam(new String[]{"hello", "world", "leetcode"},
                new String[]{"hello", "world"}));

        System.out.println(new 第416场力扣周赛().minNumberOfSeconds(
                4,
                new int[]{2, 1, 1}
        ));

        System.out.println(new 第416场力扣周赛().validSubstringCount("dcbdcdccb", "cdd"));
    }

    /**
     * 哈希表
     */
    public static boolean reportSpam(String[] message, String[] bannedWords) {

        Map<String, Integer> messageMap = new HashMap<>();
        for (String msg : message) {
            messageMap.put(msg, messageMap.getOrDefault(msg, 0) + 1);
        }
        Set<String> bSet = new HashSet<>();
        for (String bannedWord : bannedWords) {
            bSet.add(bannedWord);
        }
        int cnt = 0;
        for (Map.Entry<String, Integer> entry : messageMap.entrySet()) {
            if (bSet.contains(entry.getKey())) {
                cnt += entry.getValue();
                if (cnt >= 2) {
                    return true;
                }
            }
        }

        return false;
    }


    /**
     * 二分答案+二元一次方程求根
     */
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {

        long maxTime = 0;
        for (int workerTime : workerTimes) {
            maxTime = Math.max(maxTime, workerTime);
        }
        long left = 0, right = maxTime * ((long) mountainHeight + (long) mountainHeight * (mountainHeight - 1) / 2);


        long ans = Long.MAX_VALUE;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (valid(mountainHeight, workerTimes, mid)) {
                ans = Math.min(ans, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

    private boolean valid(int mountainHeight, int[] workerTimes, long time) {
        long curHeight = 0;

        for (int workerTime : workerTimes) {
            curHeight += getHeight(workerTime, time);
            if (curHeight >= mountainHeight) {
                return true;
            }
        }
        return curHeight >= mountainHeight;
    }

    private long getHeight(long workerTime, long time) {

        long l = (long) (Math.sqrt(0.25D + 2 * time / workerTime) + 0.5D) - 1;
        return l;
    }


    /**
     * 滑动窗口
     */
    public long validSubstringCount(String word1, String word2) {

        int[] arr2 = new int[26];
        for (int i = 0; i < word2.length(); i++) {
            arr2[word2.charAt(i) - 'a']++;
        }
        long ans = 0;
        int left = 0, right = 0;

        int[] arr1 = new int[26];
        while (left < word1.length()) {
            if (right < word1.length() && !contains(arr1, arr2)) {
                arr1[word1.charAt(right) - 'a']++;
                right++;
                continue;
            }
            if (contains(arr1, arr2)) {
                ans += word1.length() - right + 1;
            }
            arr1[word1.charAt(left) - 'a']--;
            left++;
        }
        return ans;
    }

    // arr2 所有数是否<= arr1
    private boolean contains(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] < arr2[i]) {
                return false;
            }
        }
        return true;
    }
}
